A számelméletben egy szám partíciójának természetes számok összegére való felbontását nevezzük. Figyelembe vesszük az egy tagból álló összeget is. Két partíció azonos, ha azok csak a tagok sorrendjében térnek el.
Így 5 partíciói: 1+1+1+1+1 = 2+1+1+1 = 3+1+1 = 2+2+1 = 4+1 = 3+2 = 5.
Speciális partíciókra vonatkozó tételek[szerkesztés]
- Az n szám r-nél nem több tagú partícióinak száma megegyezik n azon partícióinak számával, ahol minden tag legfeljebb r nagyságú.
- Az n szám pontosan m tagú partícióinak száma megegyezik az n-m szám m-nél nem több tagú partícióinak számával.
- Az n különböző tagokra való partícióinak száma megegyezik n páratlan sok tagú partícióinak számával.
- (Ötszögszámok tétele) Ha
, akkor n páratlan sok tagból álló partícióinak száma megegyezik páros sok tagból álló partícióinak számával.
Adott számú tagra való bontás[szerkesztés]
Jelölje
n k tagra való felbontásainak számát.
Ekkor
![{\displaystyle p_{k}(n)=\sum _{s=1}^{k}p_{s}(n-k).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d30b2c6396d1eea0d497ffc6b70f64be0b9ec93)
Nyilván
és
.
Generátorfüggvényekkel elegánsan megadhatjuk
értékét.
Jelölje
n olyan 3 tagra való felbontásainak a számát, ahol 0-t is megengedjük összeadandóként. Nyilván
és
A jobb oldal így bontható parciális törtekre:
ahol
. A sorok együtthatóit egyenlővé téve
adódik. Mivel a három utolsó tag összege legfeljebb
azt kapjuk, hogy
értéke az
-höz legközelebb eső egész szám, másképpen
.
Általában minden k-ra teljesül a
aszimptotika.
Az n szám partícióinak számát p(n)-nel jelöljük. A fentiek szerint p(5)=7.
Legyen p(0)=1.
Ekkor p(n) generátorfüggvénye
Rámánudzsan számos oszthatósági relációt igazolt p(n)-re, például, hogy
![{\displaystyle p(5m+4)\equiv 0{\pmod {5}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e177cf29600363dcfcdc938acc68866964274815)
![{\displaystyle p(7m+5)\equiv 0{\pmod {7}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/83e580c9c11a663d370335fdff7c9ab0d1b6a277)
![{\displaystyle p(11m+6)\equiv 0{\pmod {11}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5f781258adc2f02bfd40f8204aa19e7d1fad6723)
p(n)-re aszimptotikát először 1918-ban adott G. H. Hardy és Rámánudzsan. Belátták, hogy
Bizonyításuk komplex függvénytant használt. Elemi bizonyítást adtak arra a sokkal gyengébb állításra, hogy
. Erdős 1942-ben megmutatta, hogy elemi módszerekkel sokkal tovább lehet jutni: igazolni lehet, hogy
valamilyen pozitív
-ra. Erdős és Lehmer azt is igazolta, hogy tetszőleges valós x-re azon partíciók száma, amelyek kevesebb, mint
tagot tartalmaznak, tart
-hoz.
Partíciószám számító algoritmus[szerkesztés]
Jelölje P2(n,k) n azon partícióinak számát, amelyben minden elem legfeljebb k.
Ekkor a következő összefüggések teljesülnek:
• P2(1,k) = 1,P2(n,1) = 1
• P2(n,n) = 1+P2(n,n−1)
• P2(n,k) = P2(n,n) ha n < k
• P2(n,k) = P2(n,k−1)+P2(n−k,k) ha k < n
• A megoldás: P(n) = P2(n,n)
PARTÍCIÓ(n)
Return P2(n,n)
P2(n,k)
If (k=1) Or (n=1) return 1
If k>=n return P2(n,n-1)+1
return P2(n, k-1)+P2(n-k, k)
[1]
- Freud-Gyarmati: Számelmélet
|
---|
Képlet alapján | |
---|
Számsorozat alapján | |
---|
Tulajdonság alapján | |
---|
Számrendszerfüggő | |
---|
Mintázatok |
- Iker (p, p + 2)
- Ikerprímlánc (n − 1, n + 1, 2n − 1, 2n + 1, …)
- Prímhármas (p, p + 2 vagy p + 4, p + 6)
- Prímnégyes (p, p + 2, p + 6, p + 8)
- prím n−es
- Unokatestvér (p, p + 4)
- Szexi (p, p + 6)
- Chen
- Sophie Germain (p, 2p + 1)
- Cunningham-lánc (p, 2p ± 1, …)
- Biztonságos (p, (p − 1)/2)
- Számtani sorozatban (p + a·n, n = 0, 1, …)
- Kiegyensúlyozott (egymást követő p − n, p, p + n)
|
---|
Méret alapján | |
---|
Komplex számok | |
---|
Összetett számok | |
---|
Kapcsolódó fogalmak | |
---|
Az első 100 prím | |
---|
|